1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for efficiently allocating bandwidth on service flows.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that as the use of computing devices becomes more prevalent, the need for creating networks of computing devices such that resources may be shared between the computing devices also increases. To this end, cable networks which include cable modems enable users or subscribers to share resources on the cable network. Cable operators are deploying high-speed packet-based communications systems on cable television systems that are capable of supporting a wide variety of services. Services that may be provided by cable operators using cable television systems include, but are not limited to, packet telephony services, video conferencing services, and frame relay services. Such services generally make use of a Data Over Cable Service Interface Specifications (DOCSIS) protocol.
The DOCSIS protocol allows for transparent, bi-directional transfer of Internet Protocol (IP) traffic between cable system headend and customer locations. The IP traffic is transmitted over coaxial cables or hybrid-fiber/coaxial (HFC) cables. FIG. 1a is a diagrammatic representation of a wired cable system which uses DOCSIS. A cable system 100 includes a cable mode terminating system (CMTS) 104, which is located at a headend, i.e., a service provider location. Cable system 100 also includes cable modems (CMs) 108, which are typically located at customer locations. Often, CMs 108 are in communication with computer systems, e.g., CM 108b is linked to a local area network (LAN) 116 and CM 108c is linked to a computer 112. A cable line 106 is a transmission path which enables IP traffic to be transferred between CMTS 104 and CMs 108. Typically, only one CM 108 may transmit data on cable line 106 at any given time.
While cable system 100 may be implemented by cable operators, Internet Service Providers (ISPs) or Competitive Access Service Providers (CAPs), a similar system may be implemented with respect to wireless systems. FIG. 1b is a diagrammatic representation of a wireless transmissions system which uses DOCSIS. A system 120 includes a headend 124, or hub, which is effectively connected to subscriber units 128. Headend 124 is substantially analogous to CMTS 104 of FIG. 1a and serves as a central access point, while subscriber units 128 are substantially analogous to CMs 108 of FIG. 1a. Radio Frequency (RF) link 126 is analogous to cable line 106, except that link 126 is unwired while cable line 106 is wired.
Often, when a subscriber unit or a cable modem attempts to transmit information upstream, i.e., to a headend such as a CMTS or a headend in a wireless system, the subscriber unit or cable modem may request bandwidth from the headend of the CMTS. The request may be made by sending the request using frames, which are associated with a link, that are effectively set aside for bandwidth requests. Herein and after, for ease of discussion, the transmission of information upstream will be described in terms of a headend and a subscriber unit. It should be appreciated, however, that a CMTS is substantially analogous to a headend, and a cable modem is substantially analogous to a subscriber unit.
When a subscriber unit requests bandwidth for the transmission of data, the associated headend may schedule and allocate a time for the subscriber unit to transfer data. FIG. 2 is a diagrammatic representation of the steps associated with transmitting a packet upstream from a subscriber unit. A subscriber unit 208 sends a bandwidth request to a headend 204 when subscriber unit 208 wishes to transmit a packet to headend 204. After headend 204 receives bandwidth request 220, headend 204 allocates a time for subscriber unit 208 to transmit the packet on a service flow, and sends information 222 relating to the time scheduled for transmitting the packet to subscriber unit 208. When the scheduled time arrives, i.e., when the bandwidth allocated to subscriber unit 208 is available, a packet transmission 224 occurs in which subscriber unit 208 transmits the packet to headend 204. A logic block 230 associated with subscriber unit 208 may effectively execute code which monitors when the scheduled time arrives.
In a best-effort traffic delivery system as described with respect to FIG. 2, each time subscriber unit 208 wishes to transmit a packet, subscriber unit 208 must request bandwidth allotment, regardless of whether the packet to be transmitted is concatenated or non-concatenated. Typically, the amount of time required for the bandwidth request to be transmitted and for subsequent transmission of the packet after receiving the allocation information, i.e., a round trip time, is between approximately ten milliseconds (ms) to approximately fifteen ms. With respect to FIG. 2, the time elapsed from bandwidth request 220 until packet transmission 224 constitutes the round trip time. When the round trip time is approximately ten ms, subscriber unit 208 may make a maximum of approximately 100 requests for bandwidth per second. Hence, subscriber unit 208 may send a maximum of approximately 100 packets to headend 204 each second. When the packets sent by subscriber unit 208 are concatenated, the packets are typically approximately 2000 bytes or 16,000 bits in length. As such, when only up to 100 packets may be transmitted every second, on a given service flow or identifier, a data transfer rate of approximately 1.6 Megabits per second (Mbps) is substantially the highest achievable data transfer rate.
While a 1.6 Mbps data transfer rate may be acceptable in some situations, e.g., when target subscribers or customers are small offices or home offices, bandwidth requirements are generally increasing such that a 1.6 Mbps data transfer rate may be unacceptable. In particular, many small and medium sized businesses are demanding upstream data transfer rates of up to six Mbps.
As will be appreciated by those skilled in the art, all packets that are to be transmitted upstream are transmitted on a service flow, as described in the DOCSIS 1.1 Specification by Cable Television Laboratories, Inc., which is incorporated herein by reference in its entirety. A service flow defines a transport service that is characterized by a set of quality-of-service parameters such as latency, jitter, and throughput assurances. In general, a service flow identifier defines a particular unidirectional mapping between a subscriber unit and a headend unit. The headend unit may assign one or more service flow identifiers (SFIDs) to each subscriber unit to correspond to service flows required by the subscriber unit.
To increase a data transfer rate, a headend may assign multiple service flow identifiers to a subscriber unit for the transmission of upstream service. In general, depending upon how a subscriber unit is configured, there may be between four and sixteen service flows between the subscriber unit and an associated headend. Each of the service flows may be used to offer best-effort IP service. The use of multiple service flows may alleviate bottlenecks associated with the best-effort type traffic delivery described above with respect to FIG. 2. The multiple service flows enable traffic to be divided among various service flows.
Typically, when there is more than one service flow available to a subscriber unit, the transmission of packets over the multiple service flows may be determined such that the load on the service flows may be distributed. In other words, transmission of packets may be allocated in an effort to allow the service flows to be used evenly. FIG. 3 is a diagrammatic representation of service flows between a subscriber unit and a headend. A subscriber unit 308, as shown, may be configured to have four service flows 311 over which packets may be transferred to a headend 304. DOCSIS requires that classifiers, or rules, be defined in order to map a packet to a particular service flow 311. In other words, classifiers or rules may be used to determine an appropriate service flow 311 to use to transmit a packet. Classifiers may include, but are not limited to, IP classification encodings such as a masked source IP address, a masked destination IP addresses, a protocol, a source port range, and a destination port range.
FIG. 4 is a diagrammatic representation of packets and service flows over which the packets are to be transmitted. Packets 406 that are to be transmitted by a subscriber unit to a headend unit are generally passed though a set of classifiers such that packets 406 may be matched with appropriate service flows 411. Service flows 411b-d may be quality-of-service service flows that are each expected to be used for particular types of traffic, e.g., particular service flows 411 may be reserved for video traffic or for voice traffic. If a packet 406 is consistent with either a first classifier or a second classifier, for instance, that packet 406 may be transmitted on service flow 411b. Alternatively, if a packet 406 is consistent with either a third classifier or a fourth classifier, then that packet 406 may be transmitted on service flow 411c. 
With reference to FIG. 5, the steps associated with transmitting a packet through service flows that are associated with classifiers will be described. A process 500 of transmitting a packet begins at step 502 in which a packet that is to be transmitted from a subscriber unit to a headend unit is passed through a set of known classifiers. That is, a packet is effectively compared against a set of classifiers identified by a network administrator. Once the packet is passed through the set of known classifiers, a determination is made in step 504 regarding whether the packet matches, or is otherwise associated with, a known classifier. If it is determined that the packet matches the known classifier, then process flow proceeds to step 506 in which the packet is sent on the service flow that is assigned to the classifier associated with the packet. After the packet is sent, the process of transmitting the packet is completed.
Alternatively, if it is determined in step 504 that the packet does not match a known classifier, then the packet is sent or transmitted on a primary service flow. In other words, referring back to FIG. 4, if a packet 406 is not consistent with any known classifier, that packet 406 is transmitted over a best-effort or primary service flow 411a. Once the packet is transmitted on a primary service flow, the process of transmitting the packet is completed.
In order to determine a set of classifiers, and to associate the classifiers with particular service flows, a network administrator generally must study the traffic pattern between a subscriber unit and a headend. Generally, if the traffic pattern changes, the network administrator may either have to reassociate the classifiers with different service flows, or to add new classifiers. That is, the network administrator may have to configure or reconfigure classifiers. Configuring and reconfiguring classifiers is generally time consuming. Further, it has been observed that the performance of a subscriber unit is inversely proportional to the number of classifiers associated with the subscriber unit. Hence, the more classifiers that are identified to prevent a relatively large number of packets such as packets 406 of FIG. 4 from being transferred over service flow 411a, the lower the performance of the associated subscriber unit.
Additionally, bandwidth associated with service flows may not be used efficiently when packets associated with certain classifiers are transmitted more often than other classifiers. For example, if packets of one classifier are repeatedly transmitted while packets associated with other classifiers are rarely transmitted, one service flow will generally be constantly used while the bandwidth associated with other service flows may be essentially wasted. That is, if packets are consistently a part of the same session, i.e., have the same source and destination IP addresses, then the service flow that is appropriate for that session may be constantly used while other service flows remain relatively unused.
Therefore, what is needed is an efficient method for allowing packets to be transmitted between subscriber units and a headend. That is, what is desired is a method for efficiently using the bandwidth associated with multiple service flows when transmitting packets on the service flows.